<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>归并排序</title>
  </head>
  <body>
    <script>
        //分组。知道数组分成每组只有一个元素，然后进行排序比较，一直递归比较结束
      function gbSort(arr) {
        let len = arr.length;
        if (len > 1) {
          let left = gbSort(arr.slice(0, Math.floor(len / 2)));
          let right = gbSort(arr.slice(Math.floor(len / 2), arr.length));
          arr = merge(left, right);
        }
        return arr;
      }
      function merge(left, right) {
        console.log(left)
        console.log(right)
        console.log('------')
        let result = [];
        let leftIndex = 0;
        let rightIndex = 0;
        // [4] [6,2]
        while (leftIndex < left.length && rightIndex < right.length) {
          if (left[leftIndex] < right[rightIndex]) {
            result.push(left[leftIndex]);
            leftIndex++;
          } else {
            result.push(right[rightIndex]);
            rightIndex++;
          }
        }

        // return result
        //   .concat(left.slice(leftIndex))
        //   .concat(right.slice(rightIndex));
        return result.concat(
          leftIndex < left.length
            ? left.slice(leftIndex)
            : right.slice(rightIndex)
        );
      }
      let a = gbSort([0,1,3,2,1])
      console.log(a);
    </script>
  </body>
</html>
